#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue_for_tree.h"
#define NoInfo 0


BinTree CreatBinTree();             //创建二叉树
void InorderTraversal(BinTree);     //中序遍历二叉树
Queue CreateQueue();                //创建队列
bool IsEmpty(Queue);                //检查队列是否为空
bool AddQueue(Queue, BinTree);      //添加队列结点
BinTree DeleteQueue(Queue);         //弹出队列结点


/*中序遍历InorderTraversal：对树中任一结点的访问是在遍历完其左子树后进行的，访问此节点后，再对其右子树遍历。

遍历从根节点开始，遇到每个结点时，其遍历过程为:
1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树*/
void InorderTraversal(BinTree BT)
{
    if (BT)
    {
        InorderTraversal(BT->left);
        printf(" %d", BT->data);
        InorderTraversal(BT->right);
    }
}


/*层序创建二叉树：结点的输入序列是按树的从上至下从左到右的顺序形成的，各层的空节点输入数值0。在构造二叉树过程中，需要一个队列暂时存储各节点地址

创建过程如下：
1. 输入第一个数据
- 若为0，表示此树为空，将空指针赋给根指针，树构造完毕
- 若不为0，动态分配一个节点单元，并存入数据，同时将该节点地址放入队列

2. 若队列不为空，则从队列中取一个结点地址，并建立该节点的左右孩子
- 从输入序列中读入下一个数据
  若读入数据为0，将出队结点的左孩子指针置空
  若不为0，分配一个结点单元，存入所读数值，并将其置为出队结点的左孩子，同时将此孩子地址入队
- 从输入序列中读入下一个数据
  如上操作

3. 重复第二步过程，直到队列为空，再无结点出队

4. 创建根结点后，通过scan读入子树值data，若data为0，则子树为空，若data不为0，则建立子树
*/
BinTree CreatBinTree()
{
    int data;
    BinTree BT, T;
    Queue Q = CreateQueue();                            //创建队列

    scanf("%d", &data);                                 //创建根结点，读入根结点数据
    if (data != NoInfo)
    {
      BT = (BinTree)malloc(sizeof(struct sTreeNode));   //分配根结点空间
      BT->data = data;                                  //根结点值
      BT->left = BT->right = NULL;                      //根结点的左右子树指向NULL
      AddQueue(Q, BT);                                  //将结点地址入队
    }
    else
      return NULL;

    while (!IsEmpty(Q))                                 //建立左子树
    {
      T = DeleteQueue(Q);                               //从队列中读取一个结点地址
      
      scanf("%d", &data);                               //读入左子树值
      if(data == NoInfo)                              
        T->left = NULL;                                 //如果值为0，则左子树为空
      else
      {
        T->left = (BinTree)malloc(sizeof(struct sTreeNode));  //分配左子树空间
        T->left->data = data;                           
        T->left->left = T->left->right = NULL;          //左子树的左右子树指向NULL
        AddQueue(Q, T->left);                           //左子树入队
      }

      scanf("%d", &data);                               //读入右子树值
      if (data == NoInfo)
        T->right = NULL;                                //如果值为0，则右子树为空
      else
      {
        T->right = (BinTree)malloc(sizeof(struct sTreeNode));  //分配右子树空间
        T->right->data = data;
        T->right->left = T->right->right = NULL;        //右子树的左右子树指向NULL
        AddQueue(Q, T->right);                          //右子树入队
      }
    }
    return BT;
}

/*生成队列*/
Queue CreateQueue()
{
  Queue Q = (Queue)malloc(sizeof(struct sQueue));
  Q->front = NULL;
  Q->rear = NULL;

  return Q;
}

/*判断空队列
1. 如果头指针指向NULL，则队列为空
2. 那么尾指针指向NULL，队列是否为空
*/
bool IsEmpty(Queue Q)
{
    return (Q->front == NULL);
}

/*插入队列 (插入数值)【已废弃】*/
/*
bool InsertQueue(Queue Q, int insert_number)
{
  QueueNode new_queue_node;

  new_queue_node = (QueueNode)malloc(sizeof(struct sQueueNode));
  new_queue_node->data = insert_number;
  new_queue_node->next = NULL;

  if(Q->rear == NULL)
  {
    Q->rear = new_queue_node;
    Q->front = new_queue_node;
    Q->rear->next = NULL;
  }
  else
  {
    Q->rear->next = new_queue_node;
    Q->rear = new_queue_node;
  }

  return true;
}
*/

/*插入队列 （插入结点）*/
bool AddQueue(Queue Q, BinTree insert_node)
{
  if (Q->front == NULL)
  {
    Q->rear = insert_node;
    Q->front = insert_node;
    Q->rear->next = NULL;
  }
  else
  {
    Q->rear->next = insert_node;
    Q->rear = insert_node;
  }

  return true;
}

/*删除队列结点*/
BinTree DeleteQueue(Queue Q)
{
  if(IsEmpty(Q))
  {
    printf("Queue is empty !\n");
    return NULL;
  }

  BinTree tmp;
  tmp = Q->front;
  if(Q->front == Q->rear)
    Q->front = Q->rear = NULL;
  else
    Q->front = tmp->next;

  return tmp;
}


int main()
{
  /*
  Queue example_queue;
  for (BinTree i = example_queue->front; i != NULL; i = i->next)
    printf("%d  ", i->data);
  */

  BinTree new_tree;
  new_tree = (BinTree)malloc(sizeof(struct sTreeNode));
  new_tree = CreatBinTree();

  return 0;
}